% \section{Teste de Primalidade}
% 
% A fatoração de números grandes é tida como um problema intratável, porém
% percebeu-se que saber apenas quanto a primalidade de um número é uma matéria
% distinta. Teste de primalidade pode ser modelado como um problema de decisão em
% que tem resultado \textsc{sim} para primo e \textsc{não} para composto.
% 
% Os testes são divididos em duas categorias:
% \begin{itemize}
%   \item Teste Determinístico: são testes que asseguram certeza matemática para todas as respostas.
%   \item Teste Probabilístico: são testes que contém probabilidade de erro, de incerteza. Escolhe-se 
%   um candidato aleatório e aplica-se a ele critérios que possam refutar ou
%   confirmar certa propriedade.
%   A cada rodada do teste, o candidato adquire maior probabilidade para uma resposta.
% \end{itemize}
% 
% Apesar de existir teste determinístico com tempo de execução polinomial como o
% AKS~\cite{aks04}, os testes probabilísticos, com segura margem de erro
% delimitada em $2^{-80}$ ou $2^{-100}$~\cite{iso18032}, ainda são mais eficientes.
% 
% Algoritmos probabilísticos, por sua vez, podem ser classificados em dois tipos:
% \begin{itemize}
%   \item Algoritmos de Monte Carlo: podem produzir resultado incorreto.
%   \item Algoritmos Las Vegas: podem causar falha ao tentar produzir um resultado.
% \end{itemize}
% 
% Para problemas de decisão, algoritmos de Monte Carlo são usualmente classificados como:
% \begin{itemize}
%   \item Monte Carlo com viés positivo: é sempre correto quando retorna
%   \textsc{sim}.
%   \item Monte Carlo com viés negativo: é sempre correto quanto retorna
%   \textsc{não}.
% \end{itemize}
% 
% \subsection{Teste de Miller-Rabin}
% 
% O teste de Miller-Rabin~\cite{miller76, rabin80} é um algoritmo de Monte Carlo
% com viés positivo para compositividade~\cite{stinson06}. É o teste mais
% utilizado nas soluções de criptografia e um dos mais eficientes da
% atualidade~\cite{dietz04}, portanto será usado como comparativo em seções
% posteriores.
% 
% \subsection{Teste de Frobenius Quadrático Simplificado}
% O Teste de Frobenius Quadrático Simplificado (TFQS)~\cite{sqft} foi o teste
% proposto para implementação e análise neste trabalho. Nesta versão simplificada
% do teste de Frobenius Quadrático~\cite{grantham98}, o tempo de execução foi
% reduzido para duas rodadas de Miller-Rabin e probabilidade de erro, para o pior
% caso, de $2^{-12t}$, sendo $t$ o número de rodadas.
% 
% O TFQS é um algoritmo de Monte Carlo com viés positivo para compositividade, usa
% polinômios quadráticos e o automorfismo de Frobenius.
% 
% Seja $q = p^m$ a potência de um primo $p$ e o corpo finito
% $F_q = G(q)$, $G$ a extensão de Galois.
% O \textbf{automorfismo de Frobenius} $\phi_q$ é o mapeamento na bijeção
% \begin{center}
% $ \phi : F \rightarrow F$ \\
% $z \mapsto z^q$
% \end{center}
% para todo $z \in F$.
% Para um $n$ natural ímpar e $c$ uma unidade módulo $n$,
% $R(n, c)$ denota o anel polinomial $\mathbb{Z}_n[x]/(f(x) = x^2 - c)$,
% e $R(n,c)^*$ o grupo
% multiplicativo em $R(n,c)$. Sendo $f(x)$ um polinômio mônico quadrático em
% $\mathbb{Z}_n$, se $n$ é primo e $f(x)$ é irredutível em $\mathbb{Z}_n$, então
% este anel é equivalente ao corpo finito $G(n^2)$. Felizmente, esses polinômios
% são facilmente encontrados: para $n$ primo, um polinômio quadrático em
% $\mathbb{Z}_n$ é irredutível se e somente se seu discriminante, $\Delta$, é um
% resíduo não-quadrático módulo $n$, ou seja, para o polinômio mônico $x^2 - bx
%  - c$, $\Big(\frac{b^2+4c}{n} \Big) = -1$.
% 
% $G(n^2)$ é cíclico de ordem $n^2-1$, então qualquer $z \in R(n,c)^*$ deve ter
% uma ordem dividindo $n^2-1$. Também possui um automorfismo natural, chamado
% ``conjugado'' em $R(n,c)$, que deve ser equivalente ao automorfismo de Frobenius
% $z \rightarrow z^n$ em $G(n^2)$ para $n$ primo. Além disso, sendo $n$ primo,
% $n^2-1$ é divisível por 24~\footnote{prova trivial pelo Teorema Chinês do Resto}
% e também $G(n^2)$ tem um grupo cíclico de raízes 24 de unidade, gerado por uma
% raiz primitiva.
% 
% Todas $q$-ésimas raízes de unidade $z$, se existir, satisfazem $\Phi_q(z) = 0$
% para o $q$-ésimo polinômio ciclotômico $\Phi-q$.
% 
% Para um polinômio $z = ax + b$, define-se o seguinte homomorfismo multiplicativo
% em $R(n,c)$:
% $$
% \begin{array}{l l l l}
% \bar{\cdot} \hspace{.06\textwidth} : & R(n,c) \rightarrow R(n,c),\quad & \bar{z}
% = b - ax & \text{(conjugado)}; \\
% N(\cdot) \hspace{.01\textwidth}\; : & R(n,c) \rightarrow \mathbb{Z}_n,\quad &
% N(z) = \bar{z}\cdot z = b^2 - ca^2 & \text{(norma)}.\\
% \end{array}
% $$
% A notação $(a/n)$ se refere ao símbolo de Jacobi.
% 
% 
% 
% O Algoritmo~\ref{alg:mr2} é um crivo inicial equivalente a uma rodada do teste
% de Miller-Rabin com uma base pequena. Retorna ou uma raiz oitava primitiva de
% unidade em uma extensão quadrática conveniente de $\mathbb{Z}_n$ ou uma prova
% de que $n$ é composto.
% 
% \renewcommand{\algorithmicrequire}{\textbf{Input:}}
% \renewcommand{\algorithmicensure}{\textbf{Output:}}
% 
% \begin{algorithm}[h]
% \caption{Teste de Miller-Rabin com base dois ou não-resíduo pequeno}
% \label{alg:mr2}
% 
% \begin{algorithmic}[1]
% \REQUIRE Inteiro ímpar $n$.
% \ENSURE Ou \textsc{composto} ou um inteiro $c$ tal que $(c/n) = -1$ e
% $\epsilon \in R(n,c)$ com $\epsilon^4 = -1$ (i.e. $\Phi_8(\epsilon)=0$).
% 
% \IF{$n = 3$ (mod $4$)}
%   \STATE $\alpha \gets 2^{\frac{n-3}{4}}$ (mod $n$)
%   \STATE \textbf{if} $2\alpha^2 \neq \pm1$ (mod $n$) \textbf{then return}
%   \textsc{composto}
%   \STATE \textbf{else return} $c\gets -1$, $\epsilon \gets \alpha + \alpha x$
% \ENDIF
% \IF{$n = 5$ (mod $8$)}
%   \STATE $\alpha \gets 2^{\frac{n-1}{4}}$ (mod $n$)
%   \STATE \textbf{if} $\alpha^2 \neq -1$ (mod $n$) \textbf{then return}
%   \textsc{composto}
%   \STATE \textbf{else return} $c\gets 2$, $\epsilon \gets \frac{1+\alpha}{2} x$
% \ENDIF
% \IF{$n = 1$ (mod $8$)}
%   \IF{$n$ é um quadrado perfeito} \RETURN \textsc{composto}
%   \ELSE
%     \STATE $c \gets$ valor aleatório pequeno tal que $(c/n) = -1$
%     \STATE $\alpha \gets c^{\frac{n-1}{8}}$ (mod $n$)
%     \STATE \textbf{if} $\alpha^4 \neq -1$ (mod $n$) \textbf{then return}
%     \textsc{composto}
%     \STATE \textbf{else return} $c$, $\epsilon \gets \alpha$
%   \ENDIF
% \ENDIF
% \end{algorithmic}
% \end{algorithm}
% 
% Na verdade, o Algoritmo MR2 realiza uma rodada de Miller-Rabin com base 2 caso
% $n \neq 1$ (mod $8$) e com base $c$ caso contrário. A relação $\epsilon^4 = -1$
% (mod $R(n,c)$) é evidente caso $n = 1$ (mod $8$) e facilmente verificável pelas
% representações padrões $(\pm 1 \pm \sqrt{-1})/\sqrt{2}$ das quatro raízes
% oitavas primitivas de unidade nos outros casos~\cite{sqft}.
% 
% Como foi citado, o conjugado também é um automorfismo em $R(n, c)$. O
% comportamento de Frobenius sob o conjugado é similar ao comportamento do grupo
% de decomposição como um todo.
% 
% Suponha o grupo $G$. Dois elementos $a$ e $b$ são ditos conjugados se existe um
% elemento $g \in G$ tal que $gag^{-1} = b $. Isso mostra que o conjugado é uma
% relação de equivalência e toda conjugação é um automorfismo. Logo, a não
% verificação do automorfismo de Frobenius $(z^n \neq \bar{z})$ é um certificador da
% compositividade de $n$.
% 
% O Algoritmo~\ref{alg:sqft} representa uma rodada do teste de Frobenius
% quadrático simplificado.
% 
% 
% 
% \begin{algorithm}[H]
% \caption{Rodada do TFQS}
% \label{alg:sqft}
% 
% \begin{algorithmic}[1]
% \REQUIRE Inteiro ímpar $n$, inteiro pequeno $c$ tal que $(c,n)=-1$ e o
% polinômio $\epsilon \in R(n,c)$ com $\epsilon^4 = -1$.
% \ENSURE Ou \textsc{primo} ou \textsc{composto}
% 
% \STATE Escolha $z$ aleatório $\in R(n,c)$ com $(N(z)/n)=-1$
% \IF{$z^n \neq \bar{z}$}
%   \RETURN \textsc{composto}
% \ENDIF
% \IF{$z^{\frac{n^2-1}{8}} \not\in \{\pm\epsilon, \pm\epsilon^3\}$}
%   \RETURN \textsc{composto}
% \ENDIF
% \RETURN \textsc{primo}
% \end{algorithmic}
% \end{algorithm}

\section{Primality Test} 

The factorization of large numbers is known as an infeasible problem, but it was
noticed that just knowing about the primality of a number is a distinct issue.
Primality tests can be modeled as a decision problem in which outputs
\textsc{yes} for prime and \textsc{no} for composite.

The tests fall into two categories:
\begin{itemize} 
	\item Deterministic Test: are tests that ensure mathematical certainty for all
	the answers.
	\item Probabilistic Test: tests that are likely to contain errors,
	uncertainties.
	A random candidate is chosen and it is applied criteria that can refute or 
	confirm certain property. 
	On each testing round, the candidate acquires higher probability for  a
	response.
\end{itemize} 

Although exists deterministic test that runs in polynomial time as
AKS~\cite{aks04}, probabilistic tests, with safe margin of error bounded by
$2^{-80}$ or $2^{-100}$~\cite{iso18032}, are still more efficient.

Probabilistic Algorithms, in turn, can be classified into two types:
\begin{itemize}
	\item Monte Carlo Algorithms: can produce incorrect result. 
	\item Las Vegas Algorithms: can cause crashes when attempting to produce a
result.
\end{itemize} 

In decision problems, Monte Carlo algorithms are usually classified as:
\begin{itemize} 
	\item Monte Carlo with positive bias: it is always correct when returns
\textsc{yes}.
	\item Monte Carlo with negative bias: it is always correct when returns
\textsc{no}.
\end{itemize} 

\subsection{Miller-Rabin Test} 

The Miller-Rabin test~\cite{miller76, rabin80} is a Monte Carlo algorithm 
with positive bias for composite~\cite{stinson06}, in other words, when outputs
\textsc{composite} the number is a proven composite, when outputs \emph{prime}
the number is a probable prime.
It is the most used test in cryptography solutions and one of the most efficient
nowadays~\cite{dietz04} therefore, in later sections, will be used
as a contender at performance analysis.

\subsection{Simplified Quadratic Frobenius Test} 
The Simplified Quadratic Frobenius Test (SQFT)~\cite{sqft} was the 
proposed test for implementation and analysis in this work. In this simplified
version of the Quadratic Frobenius Test~\cite{grantham98}, the run time was 
reduced to the equivalent of two rounds of Miller-Rabin and worst-case error
probability of $2 ^{-12t}$, for $t$ the number of rounds.

The SQFT is a Monte Carlo algorithm with a positive bias for composite,
uses quadratic polynomials and the Frobenius automorphism.

Let $q = p^m$ a power of a prime $p$ and the finite field $F_q = G(q)$, $G$
Galois extension.
The \textbf{Frobenius automorphism} $\phi_q$ is the bijection mapping
\begin{center} 
$\Phi: F \rightarrow F$ \\
$z \mapsto z^q$ 
\end{center} 
for every $z \in F$. 
For an odd natural $n$ and $c$ a unit modulus $n$, 
$R(n, c)$ denotes the polynomial ring $\mathbb{Z}_n[x] / (f(x) = x^ 2-c)$, and
$R(n, c)^*$ the multiplicative group of units in $R(n, c)$. Since $f(x)$ is a
monic quadratic polynomial in $\mathbb{Z}_n$, if $n$ is prime and $f(x) $ is
irreducible in $\mathbb{Z}_n $, then this ring is equivalent to the finite field
$G(n^2) $. Fortunately, these polynomials are easily found: for $n$ prime, a
quadratic polynomial in $\mathbb{Z}_n $ is irreducible if and only if its
discriminant $\Delta$ is a quadratic non-residue modulo $n$, in other words, for
the monic polynomial $x^2 - bx - c$, $\Big(\frac{b^2+4c}{n} \Big) = -1$.

$G (n^2)$ is cyclic of order $n^2-1 $, so any $z \in R(n, c)^ *$ must have an
order dividing $n^2-1 $. It also has a natural automorphism, called
``conjugation'' in $R(n, c)$, which must be equivalent to the Frobenius
automorphism $z \rightarrow z^n$ in $ G(n^2)$ for prime $n$. Furthermore,
if $n$ is prime, $n^2-1$ is divisible by 24~\footnote{trivial proof by
Chinese Remainder Theorem} and also $G(n^2)$ has a cyclic group of 24-th roots
of unity, generated by a primitive root.

All $q$-th roots of unity $z$, if exists, satisfies $\Phi_q(z) = 0$ for
$q$-th cyclotomic polynomial $\Phi-q$.

For a polynomial $z = ax + b$, is defined the following multiplicative
homomorphism at $R(n, c) $: 
$$ 
\begin{array}{l l l l}
\bar{\cdot} \hspace{.06 \textwidth}: & R(n, c) \rightarrow R(n, c) \quad & \bar{z} 
= b - ax & \text{(conjugation)}; \\
N(\cdot) \hspace{.01 \textwidth} \; : & R(n, c) \rightarrow \mathbb{Z}_n, \quad & 
N(z) = \bar{z} \cdot z = b^2 - ca^2 & \text{(norm)} \\
\end{array} 
$$ 
The notation $(a/n)$ refers to the Jacobi symbol. 



Algorithm~\ref{alg:mr2} (MR2) is an initial sieve equivalent to a single
round of Miller-Rabin test with a small basis. It either outputs a primitive
8-th root of unity in a convenient extension of $\mathbb{Z}_n$ or proves
that $n$ is composite. 

\renewcommand{\algorithmicrequire}{\textbf{Input:}} 
\renewcommand{\algorithmicensure}{\textbf{Output:}} 

\begin{algorithm} [h] 
\caption{Miller-Rabin test with basis two or small non-residue} 
\label{alg:mr2} 

\begin{algorithmic} [1] \REQUIRE Odd integer $ n $.
\ENSURE Either \textsc{composite} or an integer $c$ such that $(c/ n) = -1$ and
$\epsilon \in R(n, c)$ with $\epsilon^4 = -1$ (i.e. $\Phi_8(\epsilon) = 0$).

\IF{$n = 3$ (mod $4$)}
  \STATE $\alpha \gets 2^{\frac{n-3}{4}}$ (mod $n$) \STATE \textbf{if}
  $2\alpha^2 \neq \pm1$ (mod $n$) \textbf{then return}
  \textsc{composite}
  \STATE \textbf{else return} $c\gets -1$, $\epsilon \gets \alpha + \alpha x$
\ENDIF
\IF{$n = 5$ (mod $8$)}
  \STATE $\alpha \gets 2^{\frac{n-1}{4}}$ (mod $n$) \STATE \textbf{if} $\alpha^2
  \neq -1$ (mod $n$) \textbf{then return}
  \textsc{composite}
  \STATE \textbf{else return} $c\gets 2$, $\epsilon \gets \frac{1+\alpha}{2} x$
\ENDIF
\IF{$n = 1$ (mod $8$)}
  \IF{$n$ is a perfect square} \RETURN \textsc{composite}
  \ELSE
    \STATE $c \gets$ small random value such that $(c/n) = -1$ \STATE $\alpha
    \gets c^{\frac{n-1}{8}}$ (mod $n$) \STATE \textbf{if} $\alpha^4 \neq -1$
    (mod $n$) \textbf{then return}
    \textsc{composite}
    \STATE \textbf{else return} $c$, $\epsilon \gets \alpha$
  \ENDIF
\ENDIF
\end{algorithmic}
\end{algorithm}

In fact, the MR2 algorithm performs a single round of Miller-Rabin with basis 2
in case $n \neq 1$ (mod $8$) and with basis $c$ otherwise. The relation
$\epsilon^4 = -1$ (mod $R(n, c)$) is evident in case $n = 1$ (mod $8$) and
easily verifiable by standard representations $(\pm 1 \pm \sqrt{-1})/\sqrt{2}$
of the four primitive 8-th roots of unity in other cases~\cite{sqft}.

As mentioned, the conjugation is also an automorphism on $ R(n, c) $. The
Frobenius behavior under the conjugate is similar to the behavior of
the decomposition group as a whole.

Suppose group $G$. Two elements $a$ and $b$ are said conjugates if there is
an element $g \in G $ such that $gag^{-1} = b $. This shows that the conjugate
is an equivalence relation and the whole conjugation is an automorphism.
Therefore, the non verification of Frobenius automorphism $(z^n
\neq \bar{z})$ is a certifier of $n$ compositivity.

Algorithm~\ref{alg:sqft} is a single round of the simplified quadratic frobenius
test.

\begin{algorithm}[H]
\caption{SQFT round}
\label{alg:sqft}

\begin{algorithmic}[1] \REQUIRE Odd integer $n$, small integer $c$ such that
$(c,n)=-1$ and polynomial $\epsilon \in R(n,c)$ with $\epsilon^4 = -1$.
\ENSURE Either \textsc{prime} or \textsc{composite}

\STATE Select a random $z$ $\in R(n,c)$ with $(N(z)/n)=-1$
\IF{$z^n \neq \bar{z}$}
  \RETURN \textsc{composite}
\ENDIF
\IF{$z^{\frac{n^2-1}{8}} \not\in \{\pm\epsilon, \pm\epsilon^3\}$}
  \RETURN \textsc{composite}
\ENDIF \RETURN \textsc{prime}
\end{algorithmic}
\end{algorithm}
